import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

public class Solution1335 {
    int result=-1;

    public void doDivision(int[] mark, int[] jobDifficulty, int tmpM, int tmpD){
        if(tmpD== mark.length){
            int tmpMax=0;
            for (int i = tmpM; i < jobDifficulty.length; i++) {
                tmpMax=Math.max(tmpMax,jobDifficulty[i]);
            }
            int tmpSumMax=Arrays.stream(mark).sum()+tmpMax;
            if(result==-1||result>tmpSumMax){
                result=tmpSumMax;
            }
            return;
        }
        for (int i = tmpM; i < jobDifficulty.length- (mark.length-tmpD); i++) {
            mark[tmpD-1]=Math.max(mark[tmpD-1],jobDifficulty[i]);
            doDivision(mark.clone(),jobDifficulty,i+1,tmpD+1);
        }
    }

    public int minDifficulty(int[] jobDifficulty, int d) {
        if(jobDifficulty.length<d){
            return -1;
        }
        int[] markMax=new int[d];
        doDivision(markMax,jobDifficulty,0,1);
        return result;
    }

    public static void main(String[] args) {
        Solution1335 s=new Solution1335();
        System.out.println(s.minDifficulty(new int[]{186,398,479,206,885,423,805,112,925,656,16,932,740,292,671,360},
        4));
    }
}
